#include "uinteger.h"

#include <assert.h>

#include "uints_math.h"

void UInteger_From(UInteger *a, const UInteger *b) {
	UInts_Copy(b->ds, UINTEGER_MAX_DIGIT_SIZE, a->ds); 
}

bool UInteger_FromBytes(UInteger *a, const uint8_t *v, size_t size) {
	return UInts_AssignBytes(a->ds, UINTEGER_MAX_DIGIT_SIZE, v, size);
}

bool UInteger_FromUInt(UInteger *a, uint32_t v) {
	return UInts_AssignUInt(a->ds, UINTEGER_MAX_DIGIT_SIZE, v);
}

bool UInteger_FromUInts(UInteger *a, const uint32_t *v, size_t vsize) {
	return UInts_Assign(a->ds, UINTEGER_MAX_DIGIT_SIZE, v, vsize);
}


bool UInteger_ToBytes(const UInteger* a, uint8_t *v, size_t size) {
	return UInts_ToBytes(a->ds, UINTEGER_MAX_DIGIT_SIZE, v, size);
}

void UInteger_Fill(UInteger *a, uint32_t filling) {
	UInts_Fill(a->ds, UINTEGER_MAX_DIGIT_SIZE, filling);
}

int UInteger_Compare(const UInteger *a, const UInteger *b) {
	return UInts_Compare(a->ds, UINTEGER_MAX_DIGIT_SIZE, b->ds, UINTEGER_MAX_DIGIT_SIZE);
}

int UInteger_CompareUInt(const UInteger *a, uint32_t b) {
	return UInts_Compare(a->ds, UINTEGER_MAX_DIGIT_SIZE, &b, 1);
}

int UInteger_CompareUInts(const UInteger *a, const uint32_t *b, size_t bsize) {
	return UInts_Compare(a->ds, UINTEGER_MAX_DIGIT_SIZE, b, bsize);
}

void UInteger_Copy(const UInteger *a, UInteger *b) {
	UInts_Copy(a->ds, UINTEGER_MAX_DIGIT_SIZE, b->ds); 
}

size_t UInteger_DigitSize(const UInteger *a) {
	return UINTEGER_MAX_DIGIT_SIZE;
}

uint32_t UInteger_GetDigit(const UInteger *a, size_t i) {
	return a->ds[i];
}

size_t UInteger_BitSize(const UInteger *a) {
	return UINTEGER_MAX_DIGIT_SIZE*UInteger_DigitBitSize(a);
}

bool UInteger_GetBit(const UInteger *a, size_t i) {
	size_t digitBitSize = UInteger_DigitBitSize(a);
	size_t mainIndex = i / digitBitSize;
	size_t subIndex = digitBitSize - 1 - i % UInteger_DigitBitSize(a);

	return (UInteger_GetDigit(a, mainIndex) & (1<<subIndex)) != 0;
}

size_t UInteger_DigitBitSize(const UInteger *a) {
	return sizeof(uint32_t)*8;
}

bool UInteger_Add(const UInteger *a, const UInteger *b, UInteger *c) {
	
	return UInts_Add(a->ds, UINTEGER_MAX_DIGIT_SIZE, b->ds, UINTEGER_MAX_DIGIT_SIZE, 
			         c->ds, UINTEGER_MAX_DIGIT_SIZE);
}


bool UInteger_Sub(const UInteger *a, const UInteger *b, UInteger *c) {
	assert(a != NULL && b != NULL);
	UInts_Sub(a->ds, UINTEGER_MAX_DIGIT_SIZE, b->ds, UINTEGER_MAX_DIGIT_SIZE, 
			  c->ds, UINTEGER_MAX_DIGIT_SIZE);
	return c->ds[0] > a->ds[0];
}

bool UInteger_Mul(const UInteger *a, const UInteger *b, UInteger *l, UInteger *h) {
	assert(a != NULL && b != NULL);
	uint32_t r[UINTEGER_MAX_DIGIT_SIZE*2];
	UInts_Mul(a->ds, UINTEGER_MAX_DIGIT_SIZE, b->ds, UINTEGER_MAX_DIGIT_SIZE,
		r, UINTEGER_MAX_DIGIT_SIZE*2);

	if (l != NULL) UInts_Copy(r+UINTEGER_MAX_DIGIT_SIZE, UINTEGER_MAX_DIGIT_SIZE, l->ds);
	if (h != NULL) UInts_Copy(r, UINTEGER_MAX_DIGIT_SIZE, h->ds);

	return UInts_IsZero(r, UINTEGER_MAX_DIGIT_SIZE);
}

bool UInteger_Div(const UInteger *a, const UInteger *b, UInteger *l, UInteger *h) {
	assert(a != NULL && b != NULL);
	UInts_Div(a->ds, UINTEGER_MAX_DIGIT_SIZE, b->ds, UINTEGER_MAX_DIGIT_SIZE, 
	 	  	  l!=NULL?l->ds:NULL, UINTEGER_MAX_DIGIT_SIZE,  
			  h!=NULL?h->ds:NULL, UINTEGER_MAX_DIGIT_SIZE);
	
}


void UInteger_ModAdd(const UInteger *a, const UInteger *b, const UInteger *m, UInteger *c) {
	uint32_t t[UINTEGER_MAX_DIGIT_SIZE+1];

	UInts_Add(a->ds, UINTEGER_MAX_DIGIT_SIZE, b->ds, UINTEGER_MAX_DIGIT_SIZE, 
	          t, UINTEGER_MAX_DIGIT_SIZE+1);
	UInts_Div(t, UINTEGER_MAX_DIGIT_SIZE+1, m->ds, UINTEGER_MAX_DIGIT_SIZE, 
	          NULL, 0, c->ds, UINTEGER_MAX_DIGIT_SIZE);
}

void UInteger_ModSub(const UInteger *a, const UInteger *b, const UInteger *m, UInteger *c) {
	UInteger t;	// 保证a,b,m,c可以相同
	if (UInteger_Compare(a, b) >= 0) {
		UInteger_Sub(a, b, &t);
		UInteger_Div(&t, m, NULL, c);
	} else {
		UInteger_Sub(b, a, &t);
		UInteger_Div(&t, m, NULL, &t);
		UInteger_Sub(m, &t, c);
	}
}

void UInteger_ModMul(const UInteger *a, const UInteger *b, const UInteger *m, UInteger *c) {
	uint32_t t[UINTEGER_MAX_DIGIT_SIZE*2];

	UInts_Mul(a->ds, UINTEGER_MAX_DIGIT_SIZE, b->ds, UINTEGER_MAX_DIGIT_SIZE, 
	          t, UINTEGER_MAX_DIGIT_SIZE*2);
	
	UInts_Div(t, UINTEGER_MAX_DIGIT_SIZE*2, m->ds, UINTEGER_MAX_DIGIT_SIZE, 
	          NULL, 0, c->ds, UINTEGER_MAX_DIGIT_SIZE);
}

bool UInteger_ModDiv(const UInteger *a, const UInteger *b, const UInteger *m, UInteger *c) {
	UInteger invb;

	if (UInteger_ModInv(b, m, &invb)) {
		UInteger_ModMul(a, &invb, m, c);
		return true;
	} else {
		UInteger_FromUInt(c, 0);
		return false;
	}

}

bool UInteger_ModInv(const UInteger *a, const UInteger *m, UInteger *c) {
	UInteger x[2];
	UInteger y[2];

	UInteger_FromUInt(x, 0);
	UInteger_Copy(m, x+1);

	UInteger_FromUInt(y, 1);
	UInteger_Copy(a, y+1);

	while (UInteger_CompareUInt(y+1, 0) != 0 &&
		   UInteger_CompareUInt(y+1, 1) != 0) {
		UInteger q;

		UInteger t[2];

		UInteger_Div(x+1, y+1, &q, t+1);

		UInteger_ModMul(y, &q, m, t);
		UInteger_ModSub(x, t, m, t);

		//x[0] = y[0];
		//x[1] = y[1];
		UInteger_Copy(y, x);
		UInteger_Copy(y+1, x+1);

		UInteger_Copy(t, y);
		UInteger_Copy(t+1, y+1);
	}

	UInteger_Copy(y, c);

	return UInteger_CompareUInt(y+1, 1) == 0;
}

void UInteger_Not(const UInteger *a, UInteger *b) {
	UInts_Not(a->ds, b->ds, UINTEGER_MAX_DIGIT_SIZE);
}

void UInteger_And(const UInteger *a, const UInteger *b, UInteger *c) {
	UInts_And(a->ds, b->ds, c->ds, UINTEGER_MAX_DIGIT_SIZE);
}

void UInteger_Or(const UInteger *a, const UInteger *b, UInteger *c) {
	UInts_Or(a->ds, b->ds, c->ds, UINTEGER_MAX_DIGIT_SIZE);
}

void UInteger_Xor(const UInteger *a, const UInteger *b, UInteger *c) {
	UInts_Xor(a->ds, b->ds, c->ds, UINTEGER_MAX_DIGIT_SIZE);
}


void UInteger_BitAdd(const UInteger *a, const UInteger *b, UInteger *c) {
	UInteger_Xor(a, b, c);
}

void UInteger_BitSub(const UInteger *a, const UInteger *b, UInteger *c) {
	UInteger_BitAdd(a, b, c);
}

bool UInteger_BitMul(const UInteger *a, const UInteger *b, UInteger *c) {
	return UInts_BitMul(a->ds, UINTEGER_MAX_DIGIT_SIZE, b->ds, UINTEGER_MAX_DIGIT_SIZE, c->ds, UINTEGER_MAX_DIGIT_SIZE);
}

bool UInteger_BitDiv(const UInteger *a, const UInteger *b, UInteger *q, UInteger *r) {
	assert(a != NULL && b != NULL);
	UInts_BitDiv(a->ds, UINTEGER_MAX_DIGIT_SIZE, b->ds, UINTEGER_MAX_DIGIT_SIZE, 
	 	  	     q!=NULL?q->ds:NULL, UINTEGER_MAX_DIGIT_SIZE,  
			     r!=NULL?r->ds:NULL, UINTEGER_MAX_DIGIT_SIZE);
	
}

void UInteger_BitModAdd(const UInteger *a, const UInteger *b, const UInteger *m, UInteger *c) {
	UInteger t;
	UInteger_BitAdd(a, b, &t);
	UInteger_BitDiv(&t, m, NULL, c);
}

void UInteger_BitModSub(const UInteger *a, const UInteger *b, const UInteger *m, UInteger *c) {
	return UInteger_BitModAdd(a, b, m, c);
}

void UInteger_BitModMul(const UInteger *a, const UInteger *b, const UInteger *m, UInteger *c) {
	uint32_t t[2*UINTEGER_MAX_DIGIT_SIZE];

	UInts_BitMul(a->ds, UINTEGER_MAX_DIGIT_SIZE, b->ds, UINTEGER_MAX_DIGIT_SIZE, t, 2*UINTEGER_MAX_DIGIT_SIZE);
	UInts_BitDiv(t, 2*UINTEGER_MAX_DIGIT_SIZE, m->ds, UINTEGER_MAX_DIGIT_SIZE, NULL, 0, c->ds, UINTEGER_MAX_DIGIT_SIZE);
}


bool UInteger_BitModInv2(const UInteger *a, const UInteger *m, UInteger *c) {
	UInteger x[2];
	UInteger y[2];

	UInteger_FromUInt(x, 0);
	UInteger_Copy(m, x+1);

	UInteger_FromUInt(y, 1);
	UInteger_Copy(a, y+1);

	while (UInteger_CompareUInt(y+1, 0) != 0 &&
		   UInteger_CompareUInt(y+1, 1) != 0) {
		UInteger q;

		UInteger t[2];

		UInteger_BitDiv(x+1, y+1, &q, t+1);

		UInteger_BitModMul(y, &q, m, t);
		UInteger_BitModSub(x, t, m, t);

		//x[0] = y[0];
		//x[1] = y[1];
		UInteger_Copy(y, x);
		UInteger_Copy(y+1, x+1);

		UInteger_Copy(t, y);
		UInteger_Copy(t+1, y+1);
	}

	UInteger_Copy(y, c);

	return UInteger_CompareUInt(y+1, 1) == 0;
}

void UInteger_BitModDiv(const UInteger *a, const UInteger *b, const UInteger *m, UInteger *c) {
	UInteger invb;

	UInteger_BitModInv2(b, m, &invb);
	UInteger_BitModMul(a, &invb, m, c);

}

void UInteger_BitModInv(const UInteger *a, const UInteger *m, UInteger *c) {
	uint32_t index = UInts_HighestBit(m->ds, UINTEGER_MAX_DIGIT_SIZE);

	UInteger exp;
	UInteger_FromUInt(&exp, 1);
	UInteger_LeftShift(&exp, index, &exp);

	UInteger two;
	UInteger_FromUInt(&two, 2);

	UInteger_Sub(&exp, &two, &exp);

	UInteger_BitModPow(a, &exp, m, c);

}

bool UInteger_LeftShift(const UInteger *a, size_t bits, UInteger *b) {
	assert(a != NULL && b != NULL);

	return UInts_LeftShift(a->ds, UINTEGER_MAX_DIGIT_SIZE, bits, b->ds, UINTEGER_MAX_DIGIT_SIZE);
}

void UInteger_BitModPow(const UInteger *a, const UInteger *k, const UInteger *m,  UInteger *b) {

	size_t bitsize = UInteger_BitSize(k);
	size_t firstbit = 0;
	for (; firstbit<bitsize; ++firstbit) {
		if (UInteger_GetBit(k, firstbit)) {
			UInteger_Copy(a, b);
			break;
		}
	}

	for (size_t i=firstbit+1; i<bitsize; ++i) {
		UInteger_BitModMul(b, b, m, b);
		if (UInteger_GetBit(k, i)) {
			UInteger_BitModMul(b, a, m, b);
		}
	}
}
